package com.learn.acm.utils;

import com.learn.acm.po.TreeNode;
import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 树的相关操作
 * @author zhongyuan
 */
@Slf4j
public class TreeNodeUtils {


    /**
     * 构造二叉树
     * @param nodes 节点，按层输入
     * @return
     */
    public static TreeNode createTreeNode(List<Integer> nodes) {
        if (null == nodes || nodes.size() <= 0) {
            return null;
        }
        TreeNode root = new TreeNode(nodes.get(0));
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
        int point = 1;
        while (!nodeQueue.isEmpty() && point < nodes.size()) {
            TreeNode node = nodeQueue.poll();
            if (null == node) {
                continue;
            }
            Integer leftVal = nodes.get(point++);
            node.left = null == leftVal ? null : new TreeNode(leftVal);
            if (point >= nodes.size()) {
                break;
            }
            Integer rightVal = nodes.get(point++);
            node.right = null == rightVal ? null : new TreeNode(rightVal);
            nodeQueue.offer(node.left);
            nodeQueue.offer(node.right);
        }
        return root;
    }

    /**
     * 中序遍历二叉树
     * @param root 根节点
     * @return
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        readNode(root,result);
        return result;
    }

    private static void readNode(TreeNode node, List result) {
        if (null == node) {
            return;
        }
        readNode(node.left,result);
        result.add(node.val);
        log.info("-->{}", node.val);
        readNode(node.right,result);
    }



}
